package com.datastructure.array;

/**
 * @author: 临晖
 * @date: 2023/10/08
 * @description:
 */


import java.awt.font.NumericShaper;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 螺旋矩阵
 */
public class Solution04 {


    /**
     * 给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
     *
     *
     * 本题思路：
     * 遵循 循环不变量原则 左闭右开
     * 然后以起始位置为基准，衍生至其它边，其它边相对于起始位置是静止的，每次起始位置改变，其他边跟着变就好
     * 因此，每次固定起始位置就好
     * @param n
     * @return
     */
    public static int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];

        int startX = 0;     //起始位置
        int startY= 0;      //起始位置
        int offset = 1;     //偏移量
        int count = 1;      //1 - n * n 的数字


        int i = 0;
        int j = 0;
        for (int num = 0; num < n / 2; num++) {
            //上边

            for (j = startY; j < n - offset; j++) {
                matrix[startX][j] = count++;            //起始
            }

            //右边
            for (i = startX; i < n - offset; i++) {
                matrix[i][j] = count++;
            }

            //下边
            for (; j > startY; j--) {
                matrix[i][j] = count++;
            }

            //左边
            for (; i > startX; i--) {
                matrix[i][j] = count++;
            }

            startX++;
            startY++;
            offset++;
        }

        if (n % 2 == 1) {
            matrix[n / 2][ n / 2] = count;
        }


        return matrix;
    }


    /**
     * 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
     * @param matrix
     * @return
     */
    public static List<Integer> spiralOrder(int[][] matrix) {
        ArrayList<Integer> list = new ArrayList<>();
        int m = matrix.length;
        int n = matrix[0].length;

        //y
        int left = 0;
        int right = n - 1;

        //x
        int hight = 0;
        int low = m - 1;

        while(true) {
            int i;
            int j;
            //上边
            for (j = left; j <= right; j++) {
                list.add(matrix[hight][j]);
            }
            if (++hight > low) {
                break;
            }

            //左边
            for (i = hight; i <= low; i++) {
                list.add(matrix[i][right]);
            }
            if (--right < left) {
                break;
            }

            //下边
            for (j = right; j >= left; j--) {
                list.add(matrix[low][j]);
            }

            if (--low < hight) {
                break;
            }

            //右边
            for (i = low; i >= hight; i--) {
                list.add(matrix[i][left]);
            }
            if (++left > right) {
                break;
            }


        }
        return list;

    }


    /**
     *
     * 给定一个二维数组 array，请返回「螺旋遍历」该数组的结果。
     * 螺旋遍历：从左上角开始，按照 向右、向下、向左、向上 的顺序 依次 提取元素，然后再进入内部一层重复相同的步骤，直到提取完所有元素。
     *
     * @param matrix
     * @return
     */
    public static int[] spiralArray(int[][] matrix) {
        if (matrix.length == 0) {
            return new int[]{};
        }

        int m = matrix.length;      //m行  y
        int n = matrix[0].length;       //n列 x

        int[] array = new int[m * n];
        //y
        int left = 0;
        int right = n - 1;
        //x
        int first = 0;
        int last = m - 1;

        //
        int count  = 0;
        while (true) {
            //上
            for (int i = left; i <= right; i++) {
                array[count++] = matrix[first][i];
            }
            if (++first > last) {
                break;
            }

            //右
            for (int i = first; i <= last; i++) {
                array[count++] = matrix[i][right];
            }

            if (--right < left) {
                break;
            }
            //下
            for (int i = right; i >= left; i--) {
                array[count++] = matrix[last][i];
            }

            if (--last < first) {
                break;
            }

            //左
            for (int i = last; i >= first; i--) {
                array[count++] = matrix[i][left];
            }

            if (++left < right) {
                break;
            }
        }
        return array;
    }


    public static void main(String[] args) {

    }
}
